package problems.daily;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 934. 最短的桥
 * <p>https://leetcode.cn/problems/shortest-bridge/</p>
 *
 * @author habitplus
 * @since 2022/10/25 09:26
 */
public class DT934 {
    final int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

    public int shortestBridge(int[][] grid) {
        Queue<int[]> que = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        int x, y;
        int step = 0;

        computeFirstIsland(grid, que);

        while (!que.isEmpty()) {
            for (int i = que.size(); i > 0; --i) {
                int[] dd = que.poll();
                for (int[] d : dir) {
                    x = dd[0] + d[0];
                    y = dd[1] + d[1];
                    if (0 <= x && x < m && 0 <= y && y < n) {
                        if (grid[x][y] == 0) {
                            que.offer(new int[] {x, y});
                            grid[x][y] = -1;
                        } else if (grid[x][y] == 1) {
                            return step;
                        }
                    }
                }
            }
            ++step;
        }
        return step;
    }

    private void computeFirstIsland(int[][] grid, Queue<int[]> queue) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    Queue<int[]> que = new LinkedList<>();
                    int x, y;
                    que.offer(new int[] {i, j});
                    // 标记成已经访问过
                    grid[i][j] = -1;

                    while (!que.isEmpty()) {

                        for (int k = que.size(); k > 0; --k) {
                            int[] dd = que.poll();
                            queue.offer(dd);

                            for (int[] d : dir) {
                                x = dd[0] + d[0];
                                y = dd[1] + d[1];
                                if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 1) {
                                    que.offer(new int[] {x, y});
                                    grid[x][y] = -1;
                                }
                            }
                        }
                    }

                    return;
                }
            }
        }
    }
}
